Conventional digital computers process instructions of a program in accordance with fetch and execute cycles in which instructions are fetched from memory and executed by the processor. Each fetch or execute cycle may include a number of intermediate steps. For example, the processing of an instruction manipulating data may require the fetching of additional operands from memory, and the storing of data generated as a result of the execution of the instruction. Or, the processing of an instruction manipulating the control flow of the program may examine the value of the operands and alter the program flow accordingly.
In conventional low speed computers, the fetch and execute cycle are performed for one instruction at the time. That is, the fetch for the next instruction does not occur until the previous instruction has been completely processed. The hardware that is used during the fetching steps remains idle until it is needed for the next instruction.
However, the speed at which computers can process instructions and data has increased much faster than the speed at which memory can supply the instructions and data to the computer. This memory latency can be hidden by processing multiple instructions concurrently. For example, the next instruction is fetched from memory prior to storing the result of the previous instruction. This is a simple form of instruction level parallelism or pipelining.
Also, the size of computer chips has increased faster than the speed of the logic circuits on the chip. Therefore, a further performance advantage can be gained by using the larger available space on the silicon to process multiple instructions in parallel.
The total throughput of the computer can be further increased by pre-processing or accelerating the execution of certain instructions, particularly instructions which require a large number of cycles, or which may be subject to long latencies. For example, a load instruction may attempt to read data which are not stored in a local fast memory such as a cache. In this case a subsequent instruction operating on the data can not be executed until the data are read, possibly from a virtual memory device. It would be an advantage to move such instructions up in the execution sequence so that the data become available earlier.
Pre-processing of instructions is sometimes known as speculative execution. Speculative execution is also known as the condition where all of the dependencies, control and data, for the instruction are not resolvable at the time the instruction is generated.
Various techniques are known for providing speculative execution of instructions executed out of order. That is, subsequently executed instructions may supply data for previously executed instructions. Known techniques of speculative processing of instructions generally do not permit the execution of instructions which may have data dependencies, that is, instructions which consume data before the validity of the data can be determined.
Therefore, there is a need for a mechanism which allows for the speculative execution of instructions without undue restrictions, especially when instructions are executed in different orders.